{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Evaluate Boolean Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evaluateTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算布尔二叉树的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>完整二叉树</strong>&nbsp;的根，这棵树有以下特征：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>叶子节点</strong>&nbsp;要么值为&nbsp;<code>0</code>&nbsp;要么值为&nbsp;<code>1</code>&nbsp;，其中&nbsp;<code>0</code> 表示&nbsp;<code>False</code>&nbsp;，<code>1</code> 表示&nbsp;<code>True</code>&nbsp;。</li>\n",
    "\t<li><strong>非叶子节点 </strong>要么值为 <code>2</code>&nbsp;要么值为 <code>3</code>&nbsp;，其中&nbsp;<code>2</code>&nbsp;表示逻辑或&nbsp;<code>OR</code> ，<code>3</code>&nbsp;表示逻辑与&nbsp;<code>AND</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>计算</strong>&nbsp;一个节点的值方式如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果节点是个叶子节点，那么节点的 <strong>值</strong>&nbsp;为它本身，即&nbsp;<code>True</code>&nbsp;或者&nbsp;<code>False</code>&nbsp;。</li>\n",
    "\t<li>否则，<strong>计算</strong>&nbsp;两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 <strong>运算</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回根节点<em>&nbsp;</em><code>root</code>&nbsp;的布尔运算值。</p>\n",
    "\n",
    "<p><strong>完整二叉树</strong>&nbsp;是每个节点有 <code>0</code>&nbsp;个或者 <code>2</code>&nbsp;个孩子的二叉树。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong>&nbsp;是没有孩子的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/16/example1drawio1.png\" style=\"width: 700px; height: 252px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>root = [2,1,3,null,null,0,1]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>上图展示了计算过程。\n",
    "AND 与运算节点的值为 False AND True = False 。\n",
    "OR 运算节点的值为 True OR False = True 。\n",
    "根节点的值为 True ，所以我们返回 true 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>root = [0]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>根节点是叶子节点，且值为 false，所以我们返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在&nbsp;<code>[1, 1000]</code>&nbsp;之间。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 3</code></li>\n",
    "\t<li>每个节点的孩子数为&nbsp;<code>0</code> 或&nbsp;<code>2</code>&nbsp;。</li>\n",
    "\t<li>叶子节点的值为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>&nbsp;。</li>\n",
    "\t<li>非叶子节点的值为&nbsp;<code>2</code>&nbsp;或&nbsp;<code>3</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [evaluate-boolean-binary-tree](https://leetcode.cn/problems/evaluate-boolean-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [evaluate-boolean-binary-tree](https://leetcode.cn/problems/evaluate-boolean-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,null,null,0,1]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if root.val == 2:\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif root.val == 3:\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if str(root.val) == '2':\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif str(root.val) == '3':\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if str(root.val) == '2':\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif str(root.val) == '3':\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val==1\n",
    "        if root.val==2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return (l or r) if root.val is 2 else (l and r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return bool(left or right) if root.val==2 else bool(left and right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:   \n",
    "        def dfs(node):\n",
    "            if node.left is None:\n",
    "                return True if  node.val == 1 else False\n",
    "            if node.val == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            match root.val:\n",
    "                case 0:\n",
    "                    return False\n",
    "                case 1:\n",
    "                    return True\n",
    "                case 2:\n",
    "                    return dfs(root.left) or dfs(root.right)\n",
    "                case 3:\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2 :\n",
    "            return self.evaluateTree(root.right) or self.evaluateTree(root.left)\n",
    "        elif root.val == 3:\n",
    "            return  self.evaluateTree(root.right) and self.evaluateTree(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        if root.val == 2:\n",
    "            return bool(self.evaluateTree(root.left) or self.evaluateTree(root.right))\n",
    "        if root.val == 3:\n",
    "            return bool(self.evaluateTree(root.left) and self.evaluateTree(root.right))\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val==0 :\n",
    "            return False\n",
    "        if root.val==1:\n",
    "            return True\n",
    "        left_tree=self.evaluateTree(root.left)\n",
    "        right_tree=self.evaluateTree(root.right)\n",
    "        if root.val==2 or root.val==3:\n",
    "            if root.val==2:\n",
    "                return left_tree | right_tree\n",
    "            else:\n",
    "                return left_tree & right_tree\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 题目本身就是一个重复子问题\n",
    "# 我们可以求出root.left的bool值和root.right的bool值\n",
    "# 然后看root.val是or还是and 求最终结果返回即可\n",
    "# 递归出口就是叶子结点，判断root.left或者root.right是否为空即可\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val == 1\n",
    "        leftNums = self.evaluateTree(root.left)\n",
    "        rightNums = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return leftNums or rightNums\n",
    "        elif root.val == 3:\n",
    "            return leftNums and rightNums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        match root.val:\n",
    "            case 0:\n",
    "                return False\n",
    "            case 1:\n",
    "                return True\n",
    "            case 2:\n",
    "                return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            case 3:\n",
    "                return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                return True if root.val==1 else False\n",
    "            return (dfs(root.left) and dfs(root.right)) if root.val == 3 else (dfs(root.left) or dfs(root.right))\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return left or right if root.val==2 else left and right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if root.val == 2:\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif root.val == 3:\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        #print(root)\n",
    "        if root.val == 2 :\n",
    "            if self.evaluateTree(root.left) :\n",
    "                return True\n",
    "            else :\n",
    "                return self.evaluateTree(root.right)\n",
    "        elif root.val == 3 :\n",
    "            if self.evaluateTree(root.left) :\n",
    "                return self.evaluateTree(root.right)\n",
    "            else :\n",
    "                return False\n",
    "        else :\n",
    "            return root.val == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        if root.val == 3:\n",
    "            return left and right\n",
    "        return True if root.val==1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        \n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "\n",
    "        return (l or r) if root.val == 2 else (l and r) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left_val = self.evaluateTree(root.left)\n",
    "        right_val = self.evaluateTree(root.right)\n",
    "\n",
    "        if root.val == 2:\n",
    "            return left_val or right_val\n",
    "        elif root.val == 3:\n",
    "            return left_val and right_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return not not root.val\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return (l or r) if root.val is 2 else (l and r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val==3:return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        if root.val==2:return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return root.val==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if not root.right and not root.left:\n",
    "            return  root.val==1\n",
    "        if root.val==2:\n",
    "            return  self.evaluateTree(root.left) or self.evaluateTree(root.right) \n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val in [0, 1]:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        if root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else: \n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def tf(root: Optional[TreeNode])-> bool:\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == 0 :\n",
    "                return False\n",
    "            if root.val == 1 :\n",
    "                return True\n",
    "            tf(root.left)\n",
    "            tf(root.right)\n",
    "            if root:\n",
    "                if root.left:\n",
    "                    if root.val == 2:\n",
    "                        root.val = (root.left.val or root.right.val)\n",
    "                    elif root.val == 3:\n",
    "                        root.val = (root.left.val and root.right.val)\n",
    "                return root.val == 1\n",
    "        return tf(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root:\n",
    "            return bool(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return bool(left or right) if root.val==2 else bool(left and right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dg(root):\n",
    "            if not root.left:\n",
    "                return bool(root.val)\n",
    "            if root.val == 2:\n",
    "                return dg(root.left) or dg(root.right)\n",
    "            if root.val == 3:\n",
    "                return dg(root.left) and dg(root.right)\n",
    "        return dg(root)\n",
    "            \n",
    "        #     dg(root.left)\n",
    "        #     if root.left:\n",
    "        #         root.left.val = 1\n",
    "        #     else:\n",
    "        #         root.left.val = 0\n",
    "        #     dg(root.right)\n",
    "        #     if root.right:\n",
    "        #         root.right.val = 1\n",
    "        #     else:\n",
    "        #         root.right.val = 0\n",
    "        #     if root.val == 2 and root.left.val == 0 and root.right.val == 0:\n",
    "        #         return False\n",
    "        #     if root.val == 2 and root.left.val == 0 or root.right.val ==0:\n",
    "        #         return True\n",
    "        #     if root.val == 3 and root.left.val == 1 and root.right.val == 1:\n",
    "        #         return True\n",
    "        #     if root.val == 3 and root.left.val == 0 or root.right.val == 0:\n",
    "        #         return False\n",
    "        # return dg(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2 :\n",
    "            return self.evaluateTree(root.right) or self.evaluateTree(root.left)\n",
    "        elif root.val == 3:\n",
    "            return  self.evaluateTree(root.right) and self.evaluateTree(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left: return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        self.evaluateTree(root.left)\n",
    "        self.evaluateTree(root.right)\n",
    "        if root.left and root.right:\n",
    "            if root.val == 2:\n",
    "                root.val = root.left.val | root.right.val\n",
    "            elif root.val == 3:\n",
    "                root.val = root.left.val & root.right.val\n",
    "        return bool(root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.right is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        \n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "\n",
    "        return (l or r) if root.val == 2 else (l and r) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def getRes(root):\n",
    "            if root.val == 0:\n",
    "                return False\n",
    "            if root.val == 1:\n",
    "                return True\n",
    "            \n",
    "            l = getRes(root.left)\n",
    "            r = getRes(root.right)\n",
    "\n",
    "            if root.val == 2:\n",
    "                return l or r\n",
    "            if root.val == 3:\n",
    "                return l and r\n",
    "        \n",
    "        return getRes(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            v = node.val\n",
    "            if v < 2:\n",
    "                return bool(v)\n",
    "            elif v == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        elif root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        elif root.val == 0:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left and not root.right:\n",
    "            return True if root.val == 1 else False\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        if root.val == 3:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#递归算法\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            #对象调用类成员函数时，要在函数名前加上self.或者类名.\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if (root.val < 2):\n",
    "            return root.val == 1\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None or root.right is None:\n",
    "            return bool(root.val)\n",
    "        left_flag = self.evaluateTree(root.left)\n",
    "        right_flag = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left_flag or right_flag\n",
    "        elif root.val == 3:\n",
    "            return left_flag and right_flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1    #直接返回判断语句即可返回真假\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        #递归最重要一点：终止条件的返回值以及正常最后的返回值\n",
    "        #一般态可以当作返回的值判断\n",
    "        #同一root同一层级\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def find_real(root):\n",
    "            if root.left :\n",
    "                if root.val == 2 :\n",
    "                    return find_real(root.left) or find_real(root.right)\n",
    "                elif root.val == 3:\n",
    "                    return find_real(root.left) and find_real(root.right)\n",
    "            else :\n",
    "                return root.val\n",
    "        return True if find_real(root) else False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                if node.val == 2:\n",
    "                    return dfs(node.left) or dfs(node.right)\n",
    "                elif node.val == 3:\n",
    "                    return dfs(node.left) and dfs(node.right)\n",
    "            return node.val == 1\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if node.val == 2:\n",
    "                return left or right\n",
    "            if node.val == 3:\n",
    "                return left and right\n",
    "            if node.val == 0:\n",
    "                return False\n",
    "            if node.val == 1:\n",
    "                return True\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if root.left:\n",
    "            if root.val == 2:\n",
    "                return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            else:\n",
    "                return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return root.val > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        elif root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "######注意factory={0:False,1:True,2: or,3:and}  or and等操作符只能作为操作符\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    return node.val == 1\n",
    "                else:\n",
    "                    if node.val == 2:\n",
    "                        return dfs(node.left) or dfs(node.right)\n",
    "                    else:\n",
    "                        return dfs(node.left) and dfs(node.right)\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root.val <= 1: return bool(root.val)\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if not root.left and not root.right:\n",
    "            return not not root.val\n",
    "        L = self.evaluateTree(root.left)\n",
    "        R = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return L or R\n",
    "        if root.val == 3:\n",
    "            return L and R\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 相当于后序\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left and root.right:  # 非叶子结点\n",
    "                if root.val == 2:\n",
    "                    return dfs(root.left) or dfs(root.right)\n",
    "                if root.val == 3:\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "            if not root.left and not root.right:  # 叶子结点\n",
    "                return True if root.val==1 else False\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root) -> bool:\n",
    "            if not root.left and not root.right : return bool(root.val)\n",
    "            left , right = None,None\n",
    "            if root.left :\n",
    "                left = dfs(root.left)\n",
    "            if root.right :\n",
    "                right = dfs(root.right)\n",
    "            if root.val == 2 :\n",
    "                return left | right\n",
    "            return left & right\n",
    "        return dfs(root)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if not root.left and not root.right:\n",
    "            return not not root.val\n",
    "        L = self.evaluateTree(root.left)\n",
    "        R = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return L or R\n",
    "        if root.val == 3:\n",
    "            return L and R\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l =self.evaluateTree(root.left)\n",
    "        r =self.evaluateTree(root.right)\n",
    "        return l or r if root.val==2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node.val < 2:\n",
    "                return node.val\n",
    "            elif node.val == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "                \n",
    "        return bool(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def _find(n):\n",
    "            if not n.left:\n",
    "                return n.val\n",
    "            left = _find(n.left)\n",
    "            right = _find(n.right)\n",
    "            if n.val == 2:\n",
    "                return left or right\n",
    "            else:\n",
    "                return left and right\n",
    "            \n",
    "        return _find(root) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        left=self.evaluateTree(root.left)\n",
    "        right=self.evaluateTree(root.right)\n",
    "        if root.val==2:\n",
    "            return left or right\n",
    "        else:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root.val <= 1: return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        else:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            return root.val == 1\n",
    "        \n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        val = root.val\n",
    "        if val == 2:\n",
    "            return left or right\n",
    "        return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "      def dfs(root):\n",
    "        if root:\n",
    "          if not root.left and not root.right:\n",
    "            return root.val==1\n",
    "          else:\n",
    "            if root.val==2:\n",
    "              return dfs(root.left) or dfs(root.right) \n",
    "            else:\n",
    "              return dfs(root.left) and dfs(root.right) \n",
    "              \n",
    "        else:\n",
    "          return True\n",
    "      return dfs(root)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
